2269. Connected components
The undirected unweighted graph is given. Find the number of
its connected components.
Input. The
first line contains the number of vertices n (n ≤ 100) in the graph. Then, in n lines, an n
by n matrix is given – the adjacency matrix of the graph. In the i-th
row, at the j-th position, there is a 1 if vertices i and j
are connected by an edge, and 0 if there is no edge between them. The main
diagonal of the matrix contains zeroes. The matrix is symmetric with respect to
the main diagonal.
Output. Print the
number of connected components in a graph.
|
Sample
input |
Sample
output |
60 1 1 0 0 01 0 1 0 0 01 1 0 0 0 00 0 0 0 1 00 0 0 1 0 0
0 0 0 0 0 0 |
3 |
SOLUTION
graphs – connected components
Algorithm analysis
Using the disjoint-set data structure, we
can find the number of connected components in a graph.
Initially, we place each vertex in a
separate set. Each vertex is the representative of its own set. Then, for each
edge (u, v), we unite the sets containing u and
v. After processing all the edges, the number of connected components is
equal to the number of sets in the disjoint-set data structure.
Alternatively, we can solve this problem
using depth-first search. The number of dfs function calls will
be equal to the number of connected components in the graph.
Example
The graph given in a sample is as follows:
Initially place each vertex in a separate set. Each vertex is a
representative of its own set.
Next, for each
edge (u, v), unite the sets that contain u
and v. After processing all the edges,
two vertices will be in the same connected component if they have the same
representative.
The number of
connected components in the graph is equal to the number of sets in the disjoint-set data structure. The number of sets is
equal to the number of representatives, specifically the count of vertices v for which parent[v] = v. In the given example,
there are three representatives: 3, 5 and 6. Therefore, the graph has three
connected components.
Algorithm realization
Let MAX contains the
maximum number of vertices in the graph. In mas[i] the vertex number to which vertex i
points is
stored.
#define MAX 102
int mas[MAX];
The Repr
function returns the vertex number of the representative of the set that contains vertex n. Traverse
the pointer to the next element until we encounter the representative
of the set (its
pointer points to itself).
int Repr(int
n)
{
while (n !=
mas[n]) n = mas[n];
return
n;
}
The Union
function combines two sets that contain vertices x and y. Find the representatives
of the sets containing x and y. Let these representatives be x1
and y1. If x1 = y1, then x
and y are located in the same set, and in this case do nothing. Otherwise, the pointer of representative x1
is redirected to y1.
void Union(int
x,int y)
{
int x1 =
Repr(x),y1 = Repr(y);
if (x1 == y1)
return;
mas[x1] = y1;
}
The main part of the program.
Initially, each vertex points to itself (mas[i] = i).
scanf("%d",&n);
for(i = 1; i <= n; i++) mas[i] = i;
Read the adjacency matrix. For each edge (i, j), where i < j, unite the
sets that contain the vertices i and j.
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
{
scanf("%d",&value);
if (i > j)
continue;
if (value)
Union(i,j);
}
Find the number of connective components in the variable count. It equals to the number of vertices – representatives of sets (that points to themselves).
for(i = 1; i <= n; i++)
if (mas[i] ==
i) count++;
Print the answer.
printf("%d\n",count);
Algorithm realization – depth
first search
#include <stdio.h>
#include <string.h>
#define MAX 102
int n, i, j, res;
int g[MAX][MAX], used[MAX];
void dfs(int v)
{
used[v] = 1;
for(int
i = 0; i < n; i++)
if (g[v][i] && !used[i]) dfs(i);
}
int main(void)
{
scanf("%d",&n);
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
scanf("%d",&g[i][j]);
memset(used,0,sizeof(used));
res = 0;
for(i = 0; i < n; i++)
if (!used[i])
{
dfs(i);
res++;
}
printf("%d\n",res);
return 0;
}
Java realization – dfs
import java.util.*;
public class Main
{
static int g[][],
used[];
static int n;
static void dfs(int v)
{
used[v] =
1;
for(int i = 1;
i <= n; i++)
if (g[v][i] ==
1 && used[i] ==
0) dfs(i);
}
public static void
main(String[] args)
{
Scanner con = new
Scanner(System.in);
n = con.nextInt();
g = new int[n+1][n+1];
used = new int[n+1];
for(int i = 1;
i <= n; i++)
for(int j = 1;
j <= n; j++)
g[i][j] = con.nextInt();;
int res = 0;
for(int i = 1;
i <= n; i++)
if (used[i] ==
0)
{
dfs(i);
res++;
}
System.out.println(res);
con.close();
}
}
Java realization – dsu
import java.util.*;
public class Main
{
static int mas[];
static int n;
static int
Repr(int n)
{
while (n != mas[n]) n = mas[n];
return n;
}
static void
Union(int x,int y)
{
int x1 = Repr(x);
int y1 = Repr(y);
if (x1 == y1) return;
mas[x1] = y1;
}
public static void
main(String[] args)
{
Scanner con = new
Scanner(System.in);
n = con.nextInt();
mas = new int[n+1];
for(int i = 1;
i <= n; i++) mas[i] = i;
for(int i = 1;
i <= n; i++)
for(int j = 1;
j <= n; j++)
{
int val = con.nextInt();
if (i >
j) continue;
if (val ==
1) Union(i,j);
}
int count = 0;
for(int i = 1;
i <= n; i++)
if (mas[i] == i) count++;
System.out.println(count);
con.close();
}
}
Python realization – dsu
def Repr(n):
while (n !=
mas[n]): n = mas[n]
return n
def Union(x, y):
x1
= Repr(x)
y1
= Repr(y)
if (x1 == y1): return
mas[x1] = y1
n = int(input())
mas = [int(i) for i in range (n+1)]
for i in range(1,n+1):
lst = [0] + [int(j) for j in input().split()]
for j in range(1, n + 1):
if (i < j and lst[j] == 1): Union(i, j)
res = 0
for i in range(1, n+1):
if (mas[i] == i):
res += 1
print(res)
Python realization – dfs
MAX = 102
n = int(input())
g = [[0] * MAX for
_ in range(MAX)]
used = [0] * MAX
res = 0
def dfs(v):
used[v] = 1
for i in range(n):
if g[v][i] and not used[i]:
dfs(i)
for i in range(n):
row = list(map(int, input().split()))
for j in range(n):
g[i][j] = row[j]
for i in range(n):
if not used[i]:
dfs(i)
res += 1
print(res)